#include <exception>
#include "list.hpp"
#include "utils.hpp"
#include "hashTable.hpp"

const double HashTable::hashConst = ((sqrt(5.0)-1)/2);


/*********** Internal Methods***********/

int HashTable::_hashFunction(int k) const{
    return int(floor(fabs(fmod(hashConst*k,1)*arraySize)));
}

bool  HashTable::_entryIsEmpty(int index) const{
    return (arrayOfLists[index].begin() == arrayOfLists[index].end()); 
}

bool  HashTable::_entryIsEmpty(List<Game>* myArrayOfLists, int index) const{
    return (myArrayOfLists[index].begin() == myArrayOfLists[index].end()); 
}
/**
 * Goes over the give array of lists and adds all games within to the hash-table.
 * @param oldArray - array of lists holding the games to re-hash
 * @param oldArraySize - size of array
 */
void HashTable::_rehash(List<Game>* oldArray, int oldArraySize){
    assert((NULL != oldArray) && (0 != oldArraySize));
    for (int i=0; i < oldArraySize; ++i){ //re-hash all games in every list
            if (_entryIsEmpty(oldArray, i)) //skip empty cells
                continue;         
            List<Game>& listOfGames = oldArray[i]; 
            for (List<Game>::Iterator gameItrator = listOfGames.begin();
                            listOfGames.end() != gameItrator; ++ gameItrator) {
                _addToTable(*gameItrator);
            }          
        }
}
/**
 * @param game - game to insert
 * 1. Pushes a new game into the table
 * 2. Updates nonEmtyEntries
 * @note: Does not verify size limitation.
 */
void HashTable::_addToTable(const Game& game){ 
    int hashedIndex = _hashFunction(game.getId());
    arrayOfLists[hashedIndex].insertFirst(game);
    ++gamesCounter;
}

/**
 * @param id - id of game to remove
 * 1. Removes a game from the table
 * 2. Updates nonEmtyEntries
 * @note: Does not verify size limitation.
 */
void HashTable::_removeFromTable(int id){
    List<Game>& listOfGames = arrayOfLists[_hashFunction(id)]; 
    assert(listOfGames.find(isGameIdEqualTo(id)) != listOfGames.end());
    listOfGames.remove(listOfGames.find(isGameIdEqualTo(id)));
    --gamesCounter;
    assert(gamesCounter >= 0);
}

void HashTable::_resizeUp(){
    List<Game>* oldArray = arrayOfLists;
    int oldArraySize = arraySize;
    
    arrayOfLists = new List<Game>[arraySize*2];
    arraySize *=2;
    _rehash(oldArray, oldArraySize);
    delete[] oldArray;
}

void HashTable::_resizeDown(){
	List<Game>* oldArray = arrayOfLists;
    int oldArraySize = arraySize;
    
	 /**
     *  CR: How are you sure that you will never get arraySize/2 == 0?
     *   A: the only way to get arraySize/2 == 0 is if arraySize==1 or arraySize==0.  
      *     however, if arraySize == 1 than there are no games in the table,
      *     since that would imply numOfgames == arraySize which not possible 
      *     (as a stable state) in our state machine. Consider that the only way 
      *     to decrease the table's size is to remove a game, and consider the 
      *     following as a worst-case scenario:
      *     1. The array is of size n 
      *        (let's consider the cases where n is 4, 5 or 6), and there is one 
      *        game in the table. 
     *     2. we repeatedly remove and re-insert the game to decrease the 
      *       table's size.
      * 
      * In that case:
     * ArraySize  |    numOfGames
      ---------------------------
     *case 4:
      * 4               1
      * 4->2            0 //remove
      * 2               1 //insert
      * 2->1            0 
      * 1               0
      * 1->2            1 //insert
      * 2               1
     
     * case 5:
      * 5               1
      * 5->2            0 //remove
      * 2               1 //insert
      * 2->1            0 
      * 1               0
      * 1->2            1 //insert
      * 2               1
     
     * case 6:
      * 6               1
      * 6->3            0 //remove
      * 3               1 //insert
      * 3->1            0 //remove
      * 1               0
      * 1->2            1 //insert
      * 2               1
      *
      * And the for n>6 we are reduced again to the either size=2/num=1 or size=3/num1.
     */
    
    assert(arraySize/2 > 0);
    arrayOfLists = new List<Game>[arraySize/2];
    arraySize /=2;
    _rehash(oldArray, oldArraySize);
    delete[] oldArray;
}

/*********** External Methods***********/

HashTable::HashTable(int initialSize):
        arrayOfLists (new  List<Game>[initialSize]),
        arraySize(initialSize), 
        gamesCounter(0){}

HashTable::~HashTable(){
    delete[] arrayOfLists;
}


void HashTable::insert(const Game& game){
    if (isMember(game.getId()))
        throw ElementAlreadyInTableException();
    if (gamesCounter+1 == arraySize)
        _resizeUp(); 
    _addToTable(game); //updates gamesCounter
}

void HashTable::remove(int id){
    if (false == isMember(id))
        throw ElementNotInTableException();
    if (gamesCounter-1 == arraySize/4)
        _resizeDown(); 
    _removeFromTable(id); //updates gamesCounter
}

const Game* HashTable::find(int id) const{
    int hashedIndex = _hashFunction(id);
    List<Game>& listOfGames = arrayOfLists[hashedIndex];
    List<Game>::Iterator foundGameIterator = listOfGames.find(isGameIdEqualTo(id));
    if ( foundGameIterator != listOfGames.end())
        return  &(*(foundGameIterator));
    else 
        return NULL;
}

bool HashTable::isMember(int id) const{
    return find(id) != NULL;
}
